package com.sise.DP;

/**
 *      53. 最大子序和
 *
 *      给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *      输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 *      输出：6
 *      解释：连续子数组[4,-1,2,1] 的和最大，为 6
 *
 *      1、状态：nums[] 的第 i 个位置
 *      2、选择：第 i 个位置的 num[i] 是否要选择
 *      3、状态转移方程：dp[i] = Math.max(dp[i-1] + nums[i], nums[i])，拿上一个位置的 最大子序列+当前位置的值 比较 当前位置的值
 *                    dp[状态1][状态2][...] = 求最值(选择1，选择2...)
 *
 */
public class _53_maxSubArray {

    /**
     *      动态规划 (初始版本)
     *
     *      nums[] 的下标为 0 至 n-1
     *      f(n) = Math.max{ f(n-1) + nums[i] ｜ nums[i] }，比较 dp[i - 1] 添加了 num[i] 与 num[i]本身 哪个更大
     *      这里的 dp[] 是新创建一个数组，用于存储第 i 个位置的最大子序列和
     *
     *      原始数组： -2 1 -3 4 -1 2 1 -5 4
     *      dp数组：  -2 1 -2 4  3 5 6  1 5
     */
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];

        for (int i = 1; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);     // 获取上一个位置的子序列和dp[i-1] 加上 当前位置的值nums[i]，再与当前位置做比较
            if (dp[i] > res){                                   // 与最大的子序列和进行比较
                res = dp[i];
            }
        }
        return res;
    }


    /**
     *      动态规划 (简介版)
     *      由上面的解法可知，我们只需拿到上一个 dp[i - 1] 值即可，不用说创建一整个 dp 数组
     *      故此，可以简化为一个 pre 指针
     */
    public int maxSubArray_2(int[] nums) {
        int res = nums[0];
        int pre = nums[0];
        for (int i = 1; i < nums.length; i++){
            pre = Math.max(pre, pre + nums[i]);
            res = Math.max(res, pre);       // if(pre > res) res = pre;
        }
        return res;
    }
}
